/** @file
 * IPRT - Generic Doubly Linked List.
 */

 /*
  * Copyright (C) 2010-2020 Oracle Corporation
  *
  * This file is part of VirtualBox Open Source Edition (OSE), as
  * available from http://www.virtualbox.org. This file is free software;
  * you can redistribute it and/or modify it under the terms of the GNU
  * General Public License (GPL) as published by the Free Software
  * Foundation, in version 2 as it comes in the "COPYING" file of the
  * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
  * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
  *
  * The contents of this file may alternatively be used under the terms
  * of the Common Development and Distribution License Version 1.0
  * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
  * VirtualBox OSE distribution, in which case the provisions of the
  * CDDL are applicable instead of those of the GPL.
  *
  * You may elect to license modified versions of this file under the
  * terms and conditions of either the GPL or the CDDL or both.
  */
#ifndef _INCLUDE_LIST_H_
#define _INCLUDE_LIST_H_

#include "CommonDef.h"

/** @defgroup grp_rt_list    RTList - Generic Doubly Linked List
 * @ingroup grp_rt
 *
 * The list implementation is circular without any type wise distintion between
 * the list and its nodes.  This can be confusing since the list head usually
 * resides in a different structure than the nodes, so care must be taken when
 * walking the list.
 *
 * @{
 */

extern "C" {

/**
 * A list node of a doubly linked list.
 */
    typedef struct RTLISTNODE
    {
        /** Pointer to the next list node. */
        struct RTLISTNODE* pNext;
        /** Pointer to the previous list node. */
        struct RTLISTNODE* pPrev;
    } RTLISTNODE, * PRTLISTNODE, ** PPRTLISTNODE;
    /** Pointer to a const list node. */
    typedef RTLISTNODE const* PCRTLISTNODE;

    /** The anchor (head/tail) of a doubly linked list.
     *
     * @remarks Please use this instead of RTLISTNODE to indicate a list
     *          head/tail.  It makes the code so much easier to read.  Also,
     *          always mention the actual list node type(s) in the comment.  */
    typedef RTLISTNODE RTLISTANCHOR;
    /** Pointer to a doubly linked list anchor. */
    typedef RTLISTANCHOR* PRTLISTANCHOR;
    /** Pointer to a const doubly linked list anchor. */
    typedef RTLISTANCHOR const* PCRTLISTANCHOR;

    /**
     * Initialize a list.
     *
     * @param   pList               Pointer to an unitialised list.
     */
    inline void RTListInit(PRTLISTNODE pList)
    {
        pList->pNext = pList;
        pList->pPrev = pList;
    }

    /**
     * Append a node to the end of the list.
     *
     * @param   pList               The list to append the node to.
     * @param   pNode               The node to append.
     */
    inline void RTListAppend(PRTLISTNODE pList, PRTLISTNODE pNode)
    {
        pList->pPrev->pNext = pNode;
        pNode->pPrev = pList->pPrev;
        pNode->pNext = pList;
        pList->pPrev = pNode;
    }

    /**
     * Add a node as the first element of the list.
     *
     * @param   pList               The list to prepend the node to.
     * @param   pNode               The node to prepend.
     */
    inline void RTListPrepend(PRTLISTNODE pList, PRTLISTNODE pNode)
    {
        pList->pNext->pPrev = pNode;
        pNode->pNext = pList->pNext;
        pNode->pPrev = pList;
        pList->pNext = pNode;
    }

    /**
     * Inserts a node after the specified one.
     *
     * @param   pCurNode            The current node.
     * @param   pNewNode            The node to insert.
     */
    inline void RTListNodeInsertAfter(PRTLISTNODE pCurNode, PRTLISTNODE pNewNode)
    {
        RTListPrepend(pCurNode, pNewNode);
    }

    /**
     * Inserts a node before the specified one.
     *
     * @param   pCurNode            The current node.
     * @param   pNewNode            The node to insert.
     */
    inline void RTListNodeInsertBefore(PRTLISTNODE pCurNode, PRTLISTNODE pNewNode)
    {
        RTListAppend(pCurNode, pNewNode);
    }

    /**
     * Remove a node from a list.
     *
     * @param   pNode               The node to remove.
     */
    inline void RTListNodeRemove(PRTLISTNODE pNode)
    {
        PRTLISTNODE pPrev = pNode->pPrev;
        PRTLISTNODE pNext = pNode->pNext;

        pPrev->pNext = pNext;
        pNext->pPrev = pPrev;

        /* poison */
        pNode->pNext = NULL;
        pNode->pPrev = NULL;
    }

    /**
     * Remove a node from a list, returns value.
     *
     * @returns pNode
     * @param   pNode               The node to remove.
     */
    inline PRTLISTNODE RTListNodeRemoveRet(PRTLISTNODE pNode)
    {
        PRTLISTNODE pPrev = pNode->pPrev;
        PRTLISTNODE pNext = pNode->pNext;

        pPrev->pNext = pNext;
        pNext->pPrev = pPrev;

        /* poison */
        pNode->pNext = NULL;
        pNode->pPrev = NULL;

        return pNode;
    }

    /**
     * Checks if a node is the last element in the list.
     *
     * @retval  true if the node is the last element in the list.
     * @retval  false otherwise
     *
     * @param   pList               The list.
     * @param   pNode               The node to check.
     */
#define RTListNodeIsLast(pList, pNode)  ((pNode)->pNext == (pList))

     /**
      * Checks if a node is the first element in the list.
      *
      * @retval  true if the node is the first element in the list.
      * @retval  false otherwise.
      *
      * @param   pList               The list.
      * @param   pNode               The node to check.
      */
#define RTListNodeIsFirst(pList, pNode) ((pNode)->pPrev == (pList))

      /**
       * Checks if a type converted node is actually the dummy element (@a pList).
       *
       * @retval  true if the node is the dummy element in the list.
       * @retval  false otherwise.
       *
       * @param   pList               The list.
       * @param   pNode               The node structure to check.  Typically
       *                              something obtained from RTListNodeGetNext() or
       *                              RTListNodeGetPrev().  This is NOT a PRTLISTNODE
       *                              but something that contains a RTLISTNODE member!
       * @param   Type                Structure the list node is a member of.
       * @param   Member              The list node member.
       */
#define RTListNodeIsDummy(pList, pNode, Type, Member) \
         ( (pNode) == RT_FROM_MEMBER((pList), Type, Member) )
       /** @copydoc RTListNodeIsDummy */
#define RTListNodeIsDummyCpp(pList, pNode, Type, Member) \
         ( (pNode) == RT_FROM_CPP_MEMBER((pList), Type, Member) )

/**
 * Checks if a list is empty.
 *
 * @retval  true if the list is empty.
 * @retval  false otherwise.
 *
 * @param   pList               The list to check.
 */
#define RTListIsEmpty(pList)            ((pList)->pPrev == (pList))

 /**
  * Returns the next node in the list.
  *
  * @returns The next node.
  *
  * @param   pCurNode            The current node.
  * @param   Type                Structure the list node is a member of.
  * @param   Member              The list node member.
  */
#define RTListNodeGetNext(pCurNode, Type, Member) \
    RT_FROM_MEMBER((pCurNode)->pNext, Type, Member)
  /** @copydoc RTListNodeGetNext */
#define RTListNodeGetNextCpp(pCurNode, Type, Member) \
    RT_FROM_CPP_MEMBER((pCurNode)->pNext, Type, Member)

/**
 * Returns the previous node in the list.
 *
 * @returns The previous node.
 *
 * @param   pCurNode            The current node.
 * @param   Type                Structure the list node is a member of.
 * @param   Member              The list node member.
 */
#define RTListNodeGetPrev(pCurNode, Type, Member) \
    RT_FROM_MEMBER((pCurNode)->pPrev, Type, Member)
 /** @copydoc RTListNodeGetPrev */
#define RTListNodeGetPrevCpp(pCurNode, Type, Member) \
    RT_FROM_CPP_MEMBER((pCurNode)->pPrev, Type, Member)

/**
 * Returns the first element in the list (checks for empty list).
 *
 * @returns Pointer to the first list element, or NULL if empty list.
 *
 * @param   pList               List to get the first element from.
 * @param   Type                Structure the list node is a member of.
 * @param   Member              The list node member.
 */
#define RTListGetFirst(pList, Type, Member) \
    (!RTListIsEmpty(pList) ? RTListNodeGetNext(pList, Type, Member) : NULL)
 /** @copydoc RTListGetFirst */
#define RTListGetFirstCpp(pList, Type, Member) \
    (!RTListIsEmpty(pList) ? RTListNodeGetNextCpp(pList, Type, Member) : NULL)

/**
 * Returns the last element in the list (checks for empty list).
 *
 * @returns Pointer to the last list element, or NULL if empty list.
 *
 * @param   pList               List to get the last element from.
 * @param   Type                Structure the list node is a member of.
 * @param   Member              The list node member.
 */
#define RTListGetLast(pList, Type, Member) \
    (!RTListIsEmpty(pList) ? RTListNodeGetPrev(pList, Type, Member) : NULL)
 /** @copydoc RTListGetLast */
#define RTListGetLastCpp(pList, Type, Member) \
    (!RTListIsEmpty(pList) ? RTListNodeGetPrevCpp(pList, Type, Member) : NULL)

/**
 * Returns the next node in the list or NULL if the end has been reached.
 *
 * @returns The next node, or NULL if end of list.
 *
 * @param   pList               The list @a pCurNode is linked on.
 * @param   pCurNode            The current node, of type @a Type.
 * @param   Type                Structure the list node is a member of.
 * @param   Member              The list node member.
 */
#define RTListGetNext(pList, pCurNode, Type, Member) \
    ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_MEMBER((pCurNode)->Member.pNext, Type, Member) : NULL )
 /** @copydoc RTListGetNext */
#define RTListGetNextCpp(pList, pCurNode, Type, Member) \
    ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_CPP_MEMBER((pCurNode)->Member.pNext, Type, Member) : NULL )

/**
 * Returns the previous node in the list or NULL if the start has been reached.
 *
 * @returns The previous node, or NULL if end of list.
 *
 * @param   pList               The list @a pCurNode is linked on.
 * @param   pCurNode            The current node, of type @a Type.
 * @param   Type                Structure the list node is a member of.
 * @param   Member              The list node member.
 */
#define RTListGetPrev(pList, pCurNode, Type, Member) \
    ( (pCurNode)->Member.pPrev != (pList) ? RT_FROM_MEMBER((pCurNode)->Member.pPrev, Type, Member) : NULL )
 /** @copydoc RTListGetPrev */
#define RTListGetPrevCpp(pList, pCurNode, Type, Member) \
    ( (pCurNode)->Member.pPrev != (pList) ? RT_FROM_CPP_MEMBER((pCurNode)->Member.pPrev, Type, Member) : NULL )


/**
 * Removes and returns the first element in the list (checks for empty list).
 *
 * @returns Pointer to the first list element, or NULL if empty list.
 *
 * @param   pList               List to get the first element from.
 * @param   Type                Structure the list node is a member of.
 * @param   Member              The list node member.
 */
#define RTListRemoveFirst(pList, Type, Member) \
    (!RTListIsEmpty(pList) ? RT_FROM_MEMBER(RTListNodeRemoveRet((pList)->pNext), Type, Member) : NULL)
 /** @copydoc RTListRemoveFirst */
#define RTListRemoveFirstCpp(pList, Type, Member) \
    (!RTListIsEmpty(pList) ? RT_FROM_CPP_MEMBER(RTListNodeRemoveRet((pList)->pNext), Type, Member) : NULL)

/**
 * Removes and returns the last element in the list (checks for empty list).
 *
 * @returns Pointer to the last list element, or NULL if empty list.
 *
 * @param   pList               List to get the last element from.
 * @param   Type                Structure the list node is a member of.
 * @param   Member              The list node member.
 */
#define RTListRemoveLast(pList, Type, Member) \
    (!RTListIsEmpty(pList) ? RT_FROM_MEMBER(RTListNodeRemoveRet((pList)->pPrev), Type, Member) : NULL)
 /** @copydoc RTListRemoveLast */
#define RTListRemoveLastCpp(pList, Type, Member) \
    (!RTListIsEmpty(pList) ? RT_FROM_CPP_MEMBER(RTListNodeRemoveRet((pList)->pPrev), Type, Member) : NULL)

/**
 * Removes and returns the next node in the list or NULL if the end has been
 * reached.
 *
 * @returns The next node, or NULL if end of list.
 *
 * @param   pList               The list @a pCurNode is linked on.
 * @param   pCurNode            The current node, of type @a Type.
 * @param   Type                Structure the list node is a member of.
 * @param   Member              The list node member.
 */
#define RTListRemoveNext(pList, pCurNode, Type, Member) \
    ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_MEMBER(RTListNodeRemoveRet((pCurNode)->Member.pNext), Type, Member) : NULL )
 /** @copydoc RTListRemoveNext */
#define RTListRemoveNextCpp(pList, pCurNode, Type, Member) \
    ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_CPP_MEMBER(RTListNodeRemoveRet((pCurNode)->Member.pNext), Type, Member) : NULL )

/**
 * Removes and returns the previous node in the list or NULL if the start has
 * been reached.
 *
 * @returns The previous node, or NULL if end of list.
 *
 * @param   pList               The list @a pCurNode is linked on.
 * @param   pCurNode            The current node, of type @a Type.
 * @param   Type                Structure the list node is a member of.
 * @param   Member              The list node member.
 */
#define RTListRemovePrev(pList, pCurNode, Type, Member) \
    ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_MEMBER(RTListNodeRemoveRet((pCurNode)->Member.pPrev), Type, Member) : NULL )
 /** @copydoc RTListRemovePrev */
#define RTListRemovePrevCpp(pList, pCurNode, Type, Member) \
    ( (pCurNode)->Member.pNext != (pList) ? RT_FROM_CPP_MEMBER(RTListNodeRemoveRet((pCurNode)->Member.pPrev), Type, Member) : NULL )


/**
 * Enumerate the list in head to tail order.
 *
 * @param   pList               List to enumerate.
 * @param   pIterator           The iterator variable name.
 * @param   Type                Structure the list node is a member of.
 * @param   Member              The list node member name.
 */
#define RTListForEach(pList, pIterator, Type, Member) \
    for (pIterator = RTListNodeGetNext(pList, Type, Member); \
         !RTListNodeIsDummy(pList, pIterator, Type, Member); \
         pIterator = RT_FROM_MEMBER((pIterator)->Member.pNext, Type, Member) )
 /** @copydoc RTListForEach */
#define RTListForEachCpp(pList, pIterator, Type, Member) \
    for (pIterator = RTListNodeGetNextCpp(pList, Type, Member); \
         !RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
         pIterator = RT_FROM_CPP_MEMBER((pIterator)->Member.pNext, Type, Member) )


/**
 * Enumerate the list in head to tail order, safe against removal of the
 * current node.
 *
 * @param   pList               List to enumerate.
 * @param   pIterator           The iterator variable name.
 * @param   pIterNext           The name of the variable saving the pointer to
 *                              the next element.
 * @param   Type                Structure the list node is a member of.
 * @param   Member              The list node member name.
 */
#define RTListForEachSafe(pList, pIterator, pIterNext, Type, Member) \
    for (pIterator = RTListNodeGetNext(pList, Type, Member), \
         pIterNext = RT_FROM_MEMBER((pIterator)->Member.pNext, Type, Member); \
         !RTListNodeIsDummy(pList, pIterator, Type, Member); \
         pIterator = pIterNext, \
         pIterNext = RT_FROM_MEMBER((pIterator)->Member.pNext, Type, Member) )
 /** @copydoc RTListForEachSafe */
#define RTListForEachSafeCpp(pList, pIterator, pIterNext, Type, Member) \
    for (pIterator = RTListNodeGetNextCpp(pList, Type, Member), \
         pIterNext = RT_FROM_CPP_MEMBER((pIterator)->Member.pNext, Type, Member); \
         !RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
         pIterator = pIterNext, \
         pIterNext = RT_FROM_CPP_MEMBER((pIterator)->Member.pNext, Type, Member) )


/**
 * Enumerate the list in reverse order (tail to head).
 *
 * @param   pList               List to enumerate.
 * @param   pIterator           The iterator variable name.
 * @param   Type                Structure the list node is a member of.
 * @param   Member              The list node member name.
 */
#define RTListForEachReverse(pList, pIterator, Type, Member) \
    for (pIterator = RTListNodeGetPrev(pList, Type, Member); \
         !RTListNodeIsDummy(pList, pIterator, Type, Member); \
         pIterator = RT_FROM_MEMBER((pIterator)->Member.pPrev, Type, Member) )
 /** @copydoc RTListForEachReverse */
#define RTListForEachReverseCpp(pList, pIterator, Type, Member) \
    for (pIterator = RTListNodeGetPrevCpp(pList, Type, Member); \
         !RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
         pIterator = RT_FROM_CPP_MEMBER((pIterator)->Member.pPrev, Type, Member) )


/**
 * Enumerate the list in reverse order (tail to head).
 *
 * @param   pList               List to enumerate.
 * @param   pIterator           The iterator variable name.
 * @param   pIterPrev           The name of the variable saving the pointer to
 *                              the previous element.
 * @param   Type                Structure the list node is a member of.
 * @param   Member              The list node member name.
 */
#define RTListForEachReverseSafe(pList, pIterator, pIterPrev, Type, Member) \
    for (pIterator = RTListNodeGetPrev(pList, Type, Member), \
         pIterPrev = RT_FROM_MEMBER((pIterator)->Member.pPrev, Type, Member); \
         !RTListNodeIsDummy(pList, pIterator, Type, Member); \
         pIterator = pIterPrev, \
         pIterPrev = RT_FROM_MEMBER((pIterator)->Member.pPrev, Type, Member) )
 /** @copydoc RTListForEachReverseSafe */
#define RTListForEachReverseSafeCpp(pList, pIterator, pIterPrev, Type, Member) \
    for (pIterator = RTListNodeGetPrevCpp(pList, Type, Member), \
         pIterPrev = RT_FROM_CPP_MEMBER((pIterator)->Member.pPrev, Type, Member); \
         !RTListNodeIsDummyCpp(pList, pIterator, Type, Member); \
         pIterator = pIterPrev, \
         pIterPrev = RT_FROM_CPP_MEMBER((pIterator)->Member.pPrev, Type, Member) )


/**
 * Move the given list to a new list header.
 *
 * @param   pListDst            The new list.
 * @param   pListSrc            The list to move.
 */
    inline void RTListMove(PRTLISTNODE pListDst, PRTLISTNODE pListSrc)
    {
        if (!RTListIsEmpty(pListSrc))
        {
            pListDst->pNext = pListSrc->pNext;
            pListDst->pPrev = pListSrc->pPrev;

            /* Adjust the first and last element links */
            pListDst->pNext->pPrev = pListDst;
            pListDst->pPrev->pNext = pListDst;

            /* Finally remove the elements from the source list */
            RTListInit(pListSrc);
        }
        else
            RTListInit(pListDst);
    }

    /**
     * List concatenation.
     *
     * @returns nothing.
     * @param   pListDst            The destination list.
     * @param   pListSrc            The source list to concatenate.
     */
    inline void RTListConcatenate(PRTLISTANCHOR pListDst, PRTLISTANCHOR pListSrc)
    {
        if (!RTListIsEmpty(pListSrc))
        {
            PRTLISTNODE pFirst = pListSrc->pNext;
            PRTLISTNODE pLast = pListSrc->pPrev;

            pListDst->pPrev->pNext = pFirst;
            pFirst->pPrev = pListDst->pPrev;
            pLast->pNext = pListDst;
            pListDst->pPrev = pLast;

            /* Finally remove the elements from the source list */
            RTListInit(pListSrc);
        }
    }

}

#endif